import java.util.Arrays;

public class PriorityQueueMaxHeap {
    int userSize = 0;
    int[] elem;

    public PriorityQueueMaxHeap() {
        this.elem = new int[10];
    }

    public void initHeap(int[] a){
        for (int i = 0; i < a.length; i++){
            elem[i]=a[i];
            userSize++;
        }
    }
    public void createHeap() {
        int p = (userSize-1-1)/2;
        while (p >= 0) {
            shiftDown(p,userSize);
            p--;
        }
    }
    public void shiftUp(int c){
        int p = (c-1)/2;
        while (c > 0){
            if (elem[c] > elem[p]) {
                swap(p,c);
                c = p;
                p = (c-1)/2;
            }else {
                break;
            }

        }
    }
    public void shiftDown(int p,int userSize){
        int c = 2*p+1;
        while (c <= userSize) {
            if (c+1 < userSize && elem[c]<elem[c+1]) {
                c++;
            }
            if(elem[c] > elem[p]) {
                swap(p,c);
                p = c;
                c = 2*p+1;
            }else {
                break;
            }
        }
    }
    public void swap(int a,int b){
            int temp = elem[a];
            elem[a] = elem[b];
            elem[b] = temp;
    }
    public void offer(int k) {
        if (isFull()) {
            this.elem = Arrays.copyOf(elem,2*elem.length);
        }
        this.elem[userSize] = k;
        shiftUp(userSize);
        userSize++;
    }
    public boolean isFull() {
        return this.elem.length == userSize;
    }
    public void poll() {
        swap(0,userSize-1);
        userSize--;
        shiftDown(0,userSize);
    }
    public void heapSort() {
        int end = userSize-1;
        while (end > 0) {
            swap(0,end);
            shiftDown(0,end);
            end--;
        }
    }
}
